#include <bits/stdc++.h>

using namespace std;
/**
 * 递归实现的插入排序算法。插入排序是一种简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
函数 Sort 的功能是对给定的整数数组 a 进行排序，排序的范围是从索引 p 到索引 q（包含）。如果 p 大于或等于 q，则函数直接返回，因为不需要排序。否则，
 函数首先递归地对从 p 到 q-1 的子数组进行排序，然后通过一个循环将 a[q] 插入到已排序的子数组中的正确位置
 * @param a
 * @param p
 * @param q
 */
// 定义一个名为 Sort 的函数，它接受一个整数数组 a 和两个整数 p 和 q 作为参数
void Sort(int *a, int p, int q) {
    // 如果 p 大于或等于 q，则函数结束
    if (p >= q)
        return;
    // 递归调用 Sort 函数，对数组 a 中从 p 到 q-1 的元素进行排序
    Sort(a, p, q - 1);
    // 从 q-1 开始向前遍历数组 a，直到 p
    for (int i = q - 1; i >= p; i--) {
        // 如果当前元素 a[i] 小于或等于它后面的元素 a[i+1]，则停止循环
        if (a[i] <= a[i + 1])
            break;
        // 交换 a[i] 和 a[i+1] 的值
        swap(a[i], a[i + 1]);
    }
}

int main() {
    int a[] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 0};
    int n = sizeof(a) / sizeof(a[0]);
    //sort(a,a+n);
    Sort(a, 0, n - 1);//Sort a from 0(inclusive) to n-1(inclusive)
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;

    return 0;
}
